package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 找树左下角的值
 * @date 2025/4/17 12:35
 */
public class FindBottomLeftValue_513 {

    public static void main(String[] args) {
        List<Integer> vals = new ArrayList<>();
        System.out.println(vals.size());
        vals.add(1);
        System.out.println(vals.size());

    }

    /**
     * dmsxl：dfs-递归
     * <p>
     * 思路：
     * 1.显示回溯 + 隐藏回溯。
     * 2.前中后序都可以，因为没有对中节点的逻辑处理。
     */
    int maxDepth2 = Integer.MIN_VALUE;

    int res2;

    public int findBottomLeftValue4(TreeNode root) {
        // 题目要求root至少一个节点
        dfs4(root, 0);
        return res2;
    }
    public void dfs4(TreeNode node, int depth) {
        // 不判断node是否为空，是因为非空节点才会向下递归
        if (node.left == null && node.right == null) {
            if (maxDepth2 < depth) {
                maxDepth2 = depth;
                res2 = node.val;
            }
        }

        // 显示回溯
        if (node.left != null) {
            depth++;
            dfs4(node.left, depth);
            depth--;
        }

        if (node.right != null) {
            depth++;
            dfs4(node.right, depth);
            depth--;
        }

        // 隐藏回溯
        // 因为递归传入的是depth+1，对于depth来说没有更改，所以就不用进行depth--的回溯操作
//        if (node.left != null) dfs4(node.left,depth + 1);
//        if (node.right != null) dfs4(node.right,depth + 1);


    }

    /**
     * 参考dmsxl：dfs-递归
     * <p>
     * 思路：没有回溯，因为只记录最大层数首次访问的节点值
     */
    int maxDepth = Integer.MIN_VALUE;

    int res;

    public int findBottomLeftValue3(TreeNode root) {
        // 题目要求root至少一个节点
        dfs3(root, 0);
        return res;
    }

    public void dfs3(TreeNode node, int depth) {
        if (node == null) return;

        // 中
        // 记录每层首次访问的节点值
        // maxDepth记录已访问过的最大层数，保证res只记录每层的第一个节点值，也就是最左边节点值；这样最后res得到的就是最大层数的最左边节点值
        if (maxDepth < depth) {
            maxDepth = depth;
            res = node.val;
        }
        depth++;

        dfs3(node.left, depth);

        dfs3(node.right, depth);
    }

    /**
     * 个解：bfs-层序
     */
    public int findBottomLeftValue2(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = queue.poll();

                // 记录本层第一个节点的值，也就是本层最左边节点的值
                if (i == 0) result = poll.val;

                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
        }

        return result;
    }

    /**
     * 个解：dfs-递归-先序
     * <p>
     * 思路：
     * 1.最底层 最左边节点，不一定是左叶子节点，右叶子也可能是。
     * 2.那么用一个list记录每层第一个出现的节点值，最后返回list的最后一个元素，就是最后一层的最左边节点。
     * 3.curDepth这里是隐藏回溯，因为每层的深度是通过该层局部变量记录，而不是全局变量，所以不用显示回溯。
     */
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;

        List<Integer> vals = new ArrayList<>();
        dfs(root, 0, vals);
        return vals.get(vals.size() - 1);
    }

    public void dfs(TreeNode node, int depth, List<Integer> vals) {
        if (node == null) return;

        // 中
        int size = vals.size();
        int curDepth = depth;
        // 每层只记录第一个元素
        if (size <= curDepth) {
            vals.add(node.val);
        }
        curDepth++;

        // 左
        dfs(node.left, curDepth, vals);
        // 右
        dfs(node.right, curDepth, vals);
    }

}
